首页 题解

# Description

Luogu传送门

# Solution

区间dp

# 状态定义

根据套路，我们定义 dp[i][j]dp[i][j] 表示取走区间 [i,j][i, j] 的最小花费。

但是只有区间范围似乎并不好转移，因为我们也不知道区间最大值以及最小值是多少。

所以我们再定义一个 f[i][j][x][y]f[i][j][x][y] 数组，表示区间 [i,j][i, j] 中所有数在区间 [x,y][x, y]时，需要的最小花费。

注意：这里 f[i][j][x][y]f[i][j][x][y] 中不一定 [i,j][i, j] 中的最小值和最大值就是 xx 和 yy。

# 转移

这里还要进行分类讨论：

  1. 直接合并 jj 和 [i,j−1][i, j - 1] 或合并 ii 和 [i+1,j][i + 1, j]，那么转移方程就是

1
2
f[i][j][min(x, a[j])][max(y, a[j])] = min(f[i][j][min(x, a[j])][max(y, a[j])], f[i][j - 1][x][y]);
f[i][j][min(x, a[i])][max(y, a[i])] = min(f[i][j][min(x, a[i])][max(y, a[i])], f[i + 1][j][x][y]);

  1. 枚举断点 kk，先把 [i,k][i, k] 合并好之后再和 [k+1,j][k + 1, j] 合并（此时 [k+1,j][k + 1, j] 还没有合并），或先把 [k+1,j][k + 1, j] 合并好之后再和 [i,k][i, k] 合并（同理）。

1
2
for(ll k = i; k < j; k++)
    f[i][j][x][y] = min(f[i][j][x][y], min(f[i][k][x][y] + dp[k + 1][j], f[k + 1][j][x][y] + dp[i][k]));

不过好像只转移同一个方向的就够了，不知道为什么 QwQQwQ。

注意开 long longlong \ long，以及要先进行离散化。

# Code

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
#include <iostream>
#include <cstdio>
#include <algorithm>
#include <cstring>
#define ll long long

using namespace std;

const ll N = 55;
ll n, A, B;
ll a[N], b[N];
ll f[N][N][N][N], dp[N][N];

signed main(){
    scanf("%lld%lld%lld", &n, &A, &B);
    for(ll i = 1; i <= n; i++)
        scanf("%lld", &a[i]), b[i] = a[i];
    sort(b + 1, b + 1 + n);
    ll tot = unique(b + 1, b + 1 + n) - b - 1;
    memset(f, 0x3f, sizeof(f));
    memset(dp, 0x3f, sizeof(dp));
    for(ll i = 1; i <= n; i++){
        a[i] = lower_bound(b + 1, b + 1 + tot, a[i]) - b;
        f[i][i][a[i]][a[i]] = 0;
        dp[i][i] = A;
    }
    for(ll len = 2; len <= n; len++)
        for(ll i = 1; i + len - 1 <= n; i++){
            ll j = i + len - 1;
            for(ll x = 1; x <= tot; x++)
                for(ll y = 1; y <= tot; y++){
                    f[i][j][min(x, a[j])][max(y, a[j])] = min(f[i][j][min(x, a[j])][max(y, a[j])], f[i][j - 1][x][y]);
                    f[i][j][min(x, a[i])][max(y, a[i])] = min(f[i][j][min(x, a[i])][max(y, a[i])], f[i + 1][j][x][y]);
                    for(ll k = i; k < j; k++)
                        f[i][j][x][y] = min(f[i][j][x][y], min(f[i][k][x][y] + dp[k + 1][j], f[k + 1][j][x][y] + dp[i][k]));
                }
            for(ll x = 1; x <= tot; x++)
                for(ll y = 1; y <= tot; y++)
                    dp[i][j] = min(dp[i][j], f[i][j][x][y] + A + B * (b[y] - b[x]) * (b[y] - b[x]));
        }
    printf("%lld\n", dp[1][n]);
    return 0;
}

# End